1. Field of the Invention
The present invention pertains to the updating of a dictionary utilized in compression of information, such as information transmitted over a radio or air interface, for example.
2. Related Art and Other Considerations
Push-to-talk over Cellular (PoC) is being developed for handsets in networks such as GSM/GPRS networks, EDGE networks, UMTS, and code division multiple access (CDMA) systems. Push to talk over Cellular (PoC) is currently being standardized and agreed upon in an industry consortium known as the Open Mobile Alliance (OMA) forum. See, e.g., OMA PoC User Plane, OMA-UP-POC=V0—1-20041005-D, Draft Version 1.0.9 October 2004, incorporated herein by reference, and http://www.openmobilealliance.com/tech/wg_committees/poc.htm,
PoC is basically a voice chat for cellular telecommunication systems. PoC provides quick one-to-one or group communication, providing something like a short instant messaging service which feels like “walkie talkies”.
PoC enabled handsets will most likely be equipped with a PoC-button. The PoC button may (for example) be: a dedicated hardware button; an assigned button on a standard keypad; or, a software button used in e.g. pressure sensitive screens. When the PoC button is pressed, the handset is connected directly to another user or user group. In the first releases of PoC provide half-duplex service, although full duplex may be available at a later stage.
One of the important features that PoC is expected to support is a service known as “Presence”. The Presence service allows a user to obtain information about the status of one or several users in the user's contacts list whom the user has selected, included, or designated for the Presence service. The Presence information is sent to the user as Presence update messages which take the form of Session Initiation Protocol (SIP) messages. These Presence update messages may be sent according to different principles, e.g. using push or pull strategies.
As an aside, Session Initiation Protocol (SIP) is an application layer protocol for establishing, modifying, and terminating multimedia sessions or calls. These sessions may include Internet multimedia conferences, Internet telephony, and similar applications. As is understood in this art, SIP can be used over either the Transmission Control Protocol (TCP) or the User Datagram Protocol (UDP). SIP is described in such publications as: (1) Rosenberg, J. et. Al., “SIP: Session Initiation Protocol”, RFC3261, Internet Engineering Task Force, June 2002; and (2) Handley, M., Schulzrinne, H., Schooler, E. and Rosenberg, J., SIP: Session Initiation Protocol, IETF RFC 2543, 2000), both of which are incorporated herein by reference in their entirety.
SIP is an example of an Internet Protocol (IP). Other examples of Internet Protocols include Real Time Streaming Protocol (RTSP) and Session Description Protocol (SDP). Real Time Streaming Protocol (RTSP) is an application level protocol for control of delivery of data with real-time properties, such as audio and video data. RTSP may also be used with UDP, TCP, or other protocols as a transport protocol. Session Description Protocol (SDP) is used to advertise multimedia conferences and communicate conference addresses and conference tool-specific information. SDP is also used for general real-time multimedia session description purposes. SDP is carried in the message body of SIP and RTSP messages. SIP, RTSP, and SDP are all ASCII text based using the ISO 10646 character set in UTF-8 encoding.
A disadvantage with the Internet Protocol is the relatively large overhead the IP protocol suite introduces due to large headers and text-based signaling protocols. Yet it is very important in cellular systems to use the scarce radio resources in an efficient manner. In cellular systems it is important to support a sufficient number of users per cell, otherwise implementation and operation costs will be prohibitive. Frequency spectrum, and thus bandwidth, is a costly resource in cellular links and should be used efficiently to maximize system resources.
When access occurs over narrow band cellular links, compression of the protocol messages is needed to meet quality of service requirements, such as set-up time and delay. Compression of traffic over a radio link (e.g., air interface), such as from a wireless user terminal to a core network, is greatly desirable.
As currently proposed, PoC uses a compression scheme known as SigComp to compress SIP messages. SigComp is described in, e.g., the following documents (all of which are incorporated herein by reference in their entireties: Price, R. et al., “Signaling Compression (SigComp)”, Internet Engineering Task Force (IETF) RFC 3320, Internet Engineering Task Force, January 2003; Hannu, H. et al., “Signaling Compression (SigComp)—Extended Operations”, Internet Engineering Task Force (IETF) RFC 3321, December 2002; US Patent Publication US 2004/0047301.
SigComp includes a simple protocol and a Universal Decompressor Virtual Machine (UDVM). The protocol part of SigComp defines (for example) a message format and a set of rules that describe how to load information into the UDVM. The UDVM provides the decompressor functionality of SigComp. Any compressed message can be decompressed provided that the UDVM is loaded with the correct set of instructions to interpret the format of the compressed data. Further, a SigComp compressor endpoint has the ability to save information at the remote receiving decompressor endpoint in the form of states. The states are typically information from previous messages used to update a dictionary or codebook used by the compression algorithm. These states can then be retrieved by the UDVM as new compressed messages arrive.
One method for implementing a binary compression scheme is the use of dictionary based compression techniques. In general, a dictionary compression scheme uses a data structure known as a dictionary to store strings of symbols which are found in the input data. The scheme reads in input data and looks for strings of symbols which match those in the dictionary. If a string match is found, a pointer or index to the location of that string in the dictionary is output and transmitted instead of the string itself. If the index is smaller than the string it replaces, compression will occur. A decompressor contains a representation of the compressor dictionary so that the original string may be reproduced from the received index.
Binary compression algorithms, such as Deflate and LZSS, use such a dictionary, which essentially is a buffer or memory which contains data that is referenced in the compressed message. Deflate is described, e.g., by Deutsch, P. et al., “DEFLATE Compressed Data Format Specification Version 1.3”, RFC 1952, Internet Engineering Task Force, May 1996. LZSS is described, e.g., by Storer, J. A. and Szimanski, T. G., “Data compression Via Textual Substitutions”, Journal of the ACM 29, 1982.
Basically, the foundation of dictionary compression is pattern matching and substitution, i.e. finding and replacing groups of consecutive symbols (strings) with an index into a dictionary. This results in compression if the representation of the index is shorter than the string it replaces. Dictionary compression schemes are taught in one or more of the following, all of which are incorporated herein by reference in their entirety: U.S. patent application Ser. No. 09/814,407, filed Mar. 21, 2001 by Hannu et al. entitled “Communication System And Method Utilizing Request-Reply Communication Patterns for Data Compression” (see also US Patent Publication US2002/0057715); U.S. patent application Ser. No. 09/814,268, filed Mar. 21, 2001 by Hannu et al. entitled “System And Method For Communicating With Temporary Compression Tables” (see also US Patent Publication US2002/0058501); U.S. patent application Ser. No. 09/814,406, filed Mar. 21, 2001 by Hannu et al. entitled “Static Information Knowledge Used With Binary Compression Methods” (see also US Patent Publication US2002/0059462); U.S. Pat. No. 6,707,400 by Christoffersson et al. entitled “Method and Apparatus For Fast Longest Match Search”.
Compression performance depends to a large extent on the contents of the dictionary that has been saved as a SigComp state. In the most frequently used compression mode, i.e., dynamic compression, the dictionary is updated as new messages are compressed and sent. The dictionary is typically updated by adding the last message to the circular buffer that contains the dictionary.
Thus, when dynamic compression is used in SigComp, the old parts of the dictionary are shifted out when the dictionary is updated due to limited amount of memory in the dictionary. For some aspects of PoC the shifting of the dictionary contents does not cause a substantial problem. For example, for compression of SIP invite sessions (for an already established PoC session) for which SigComp has been optimized, shifting of dictionary contents is of little concern (assuming that the dictionary is of reasonably large size) since the newer parts of the dictionary typically contain more recent and more useful strings. For SigComp, the decompression memory and the state memory need to be at least 4 Kbytes to obviate the concern.
On the other hand, the shifting of dictionary contents can cause a problem under some circumstances. For example, mundane signaling related to the PoC Presence Service may flush from the dictionary earlier strings which are more useful or significant for decompression purposes. Consider, for example, what happens when a Presence Server, a node of the PoC service-providing network, sends the aforementioned Presence update messages using the SIP “Notify” method to a remote terminal (e.g., wireless terminal, mobile station, mobile terminal, etc.). The remote terminal acknowledges receipt of a SIP Presence update message by, for example, returning a SIP 200 OK message. As a consequence of doing so, the SigComp dictionary may also be updated. These Presence update messages can be quite frequent (at least compared to the session initiation signaling) and also occur during the entire time that the user is registered with the Presence Service.
Old content of the dictionary is shifted out with receipt of each Presence update message. The amount of old content which is shifted out depends on the size of the message and the size of the state memory. With such shifting, there is a risk that useful information is shifted out and deleted from the dictionary. FIG. 5 illustrates consequences of dictionary updates upon occasion of successive message receipt instances for an example illustrative dictionary when dynamic compression is used for compression of Presence-related signaling. The Presence update messages such as NOTIFY1, NOTIFY2, NOTIFY3, . . . etc. in FIG. 5 may be a list of users' status. The lists of these Presence update messages are expected to be more or less identical from message to message, e.g., the lists of consecutive messages are not likely to vary significantly and in many cases not at all. Thus, when the dynamic compression mode is used in such a case, the dictionary will end up being a number of almost identical copies of the status list or SIP 200 OKs, as shown by the last instance or update in FIG. 5. Should the user then initiates a new session (a new SIP Invite dialogue), the dictionary will be filled with less useful strings (e.g., the NOTIFY messages). These NOTIFY messages are typically not helpful for decompressing messages of a new session, rendering the dictionary less useful with the result that the compression efficiency is not as high as it potentially could be. The result is that longer time is required for signaling for setting up this new session than would have been the case if the dictionary had been left unchanged (e.g., if the dictionary had not been flushed with the Presence update NOTIFY messages). This is a serious disadvantage, since short set up time is one of the most important design goals of the PoC standard.
What is needed, therefore, and an object of the present invention, is provision of apparatus and method for judiciously handling compression dictionary updates when receiving relatively invariant messages across a radio interface.